/**
 * https://leetcode.cn/problems/maximum-sum-circular-subarray/submissions/589886976/
 * 918. 环形子数组的最大和
 * medium 2024.12.28
 * 前缀和后缀和差分
 */

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n=nums.size();
        vector<int> leftmax(n);
        leftmax[0]=nums[0];
        int sum=nums[0];
        int pre=nums[0];
        int ans=nums[0];
        for(int i=1;i<n;++i){
            pre=max(pre+nums[i],nums[i]);
            ans=max(ans,pre);
            sum+=nums[i];
            leftmax[i]=max(leftmax[i-1],sum);
        }
        int rsum=0;
        for(int i=n-1;i>0;--i){
            rsum+=nums[i];
            ans=max(ans,rsum+leftmax[i-1]);
        }
        return ans;
    }
};